17.6 Sapphire

マルチバージョンコピー法の問題点

ヒープを分割してプロセッサごとに独立してGC

ヒープの構造をマルチプロセッサのトポロジと結びつける

アプリケーションのヒープ構造によっては難しい

一部のプロセッサがボトルネックになることがある

コレクタスレッドの優先度でスループットのバランスをとる方法もある

Sapphire

多数のミューテータスレッドが存在する共有メモリ型マルチプロセッサ向け

並行レプリケーション型コピーアルゴリズムを拡張

ミューテータスレッド1つずつflipが行える

ミューテータはfromとtoの両方のオブジェクトを書き換えなければならない

toがなかった場合はfromしか書き換えない

ここのオブジェクトは回収されないが、to空間と違って走査されない

コレクタのフェーズ

MarkCopy

Mark: 到達可能なオブジェクトをマークする

PreMark: Markフェーズライトバリアをインストールする

RootMark: グローバル変数を黒くする

HeapMark/StackMark: コレクタのマークキューを処理する

Allocate: to空間シェルを割り付ける

Copy: from空間の内容をto空間シェルにコピーする

Flip

PreFlip: Flipフェーズライトバリアをインストールする

HeapFlip: 全ヒープのfrom空間ポインタをto空間へflipする

ThreadFlip: スレッドを1つずつflipする

Reclaim: from空間を回収する

MarkCopy

ルート(グローバル変数、スレッドスタック、レジスタ)から直接到達可能なオブジェクトをマークしto空間へコピー

from空間とto空間の間に緩い一貫性を維持

ミューテータはfrom空間から読み出し

ミューテータはfrom空間とともにto空間にも書き込み

JavaやC++のメモリモデルを用いて、読み出しの際のリードバリアを減らす

リードバリアが必要なのはvolatileフィールド(C++のatomic + volatile)のみ

volatileでないフィールドにおける競合は存在しないと仮定

from空間とto空間の内容は同期ポイントにおいて一致しさえすればよい

toの内容は読み出さないので

変更の反映はそれまでの間に済ませればよい

Flip中は同期ポイントの前なので、from空間とto空間の一貫性がないことに気をつける

Flip

ルートのポインタをto空間へ転送

スレッドごとにfrom空間とto空間を反転

反転前にはfrom空間とto空間のどちらのオブジェクトへの参照もありうる

他のミューテータの反転によって、to空間のオブジェクトへの参照を取得する可能性がある

今までの並行コピーGCの復習

Sapphireはリードバリアを用いずにインクリメンタルに反転

ミューテータがfrom空間とto空間に同時にアクセスするので同期が必要

ポインタの等値判定にバリアが必要

同じオブジェクトのfrom空間における参照とto空間のコピーにおける参照とは言語レベルで同じでないといけない

code:アルゴリズム17-5.cpp

// 一般のポインタ比較

// pまたはqがnullptrなら、コンパイラはpointerEQを単にoperator==に戻してよい

bool pointerEQ(void *p, void *q) {

if (p == q) return true;

if (q == nullptr) return false;

if (p == nullptr) return false;

return flipPointerEQ(p, q);

}

// Flipフェーズ中のポインタ比較

bool flipPointerEQ(void *p, void *q) {

void *pp = forward(p);

void *qq = forward(q);

return pp == qq;

}

void *forward(void *p) { // assert(p);

void *pp = toAddress(p);

if (pp == nullptr) { // pがto空間にあるとき

return p;

} else {

return pp;

}

}

ルートから到達可能なすべてのfrom空間オブジェクトをマークする

ミューテータはマーキングしないがマークさせるオブジェクトをキューへ追加する

ミューテータのライトバリアがストアしようとする未マークの参照をキューへ追加する

コレクタはすべてのマーク対象をキューから取得する

コレクタはまずルートを走査して未マークの参照をキューへ追加する

コレクタはその後キュー内のオブジェクトのマークと走査(新しい参照はまたキューへ追加)を行う

ミューテータごとに専用のキューを用意して同期しない

マークキューが空になったら、コレクタはミューテータを1つずつ走査する

ミューテータを停止して、スタックとレジスタ中の未マークの参照をキューへ追加する

ミューテータごとのマークキューもコレクタのマークキューへ追加する

すべてのミューテータに1度ずつ走査しても未マークの参照が見つからなければマーク完了

最終的にはすべてのfrom空間オブジェクトがマークされる(停止性)

ライトバリアがマーキング境界の後退を防ぐ

ルートと新しいオブジェクトを黒に保つ

ミューテータに白い参照をヒープに書き込ませない

前回の走査以降にアクティブになったミューテータ/スタックフレームだけを走査し直せば十分

三色抽象化

白: 未マークのオブジェクト

灰: マークキュー中のオブジェクト

キュー追加済みビットを導入

黒: マーク済みオブジェクト

Markフェーズの3つのステップ

PreMark: Markフェーズ用ライトバリアWrite_Mark(アルゴリズム17-6 (a))をインストール

バリアがフェーズごとに切り替わる仕組みがある

RootMark: グローバル変数中の参照をWrite_Markでキューに追加する

ライトバリアを明示的に起動する

Write_Markを用いることは本質的ではなくて、いずれにせよキューに追加すればよいと思う

HeapMark/StackMark: コレクタのマークキュー、スレッドスタックを走査する

明示的灰色集合って必要なのか？

キュー中の未マークオブジェクトを一度明示的灰色集合に移してから、明示的灰色集合中のオブジェクトを1つずつ走査している

キュー中の未マークオブジェクトを1つずつ走査するのと何が異なるのか

マークキュー中のオブジェクトのスロット内の未マークなオブジェクトをWrite_Markを用いてマークキューへ追加

マークキューが空になったあと、ミューテータのスレッドスタックを走査する

1つのミューテータスレッドをセーフポイント(ライトバリア外)で停止する

スタックとレジスタを走査して未マークのルートをすべてWrite_Markによりマークキューへ追加

code:アルゴリズム17-6.py

# (a) Markフェーズ用バリア

def Write_Mark(p, i, q):

if isFromSpace(q) && not marked(q) # 白

enqueue(q) # コレクタが後でマークする

# (b) Copyフェーズ用バリア

def Write_Copy(p, i, q):

$ pp = toAddress(p)

if pp != null: # pはfrom空間

q = forward(q) # qがポインタでないならこれは省略

# (c) Flipフェーズ用バリア

def Write_Flip(p, i, q):

q = forward(q) # qがポインタでないならこれは省略

pp = toAddress(p)

if pp != null: # pはfrom空間

return

pp = fromAddress(p)

if pp != null: # pはto空間

return

# toAddressはto空間オブジェクトに対してnullを返す

MarkCopy: Allocate

コレクタは、前のフェーズでマーク済みのfrom空間オブジェクトのそれぞれに対して、空の「シェル」を割り付ける

シェル: to空間のコピー

from空間にシェルを指す転送ポインタをセット

シェルからfrom空間のオブジェクトを引いてくるハッシュ表を構築

from空間をto空間とflipしたミューテータは、その後も未だにfrom空間を参照する他のミューテータのために、to空間の更新をfrom空間に反映する必要がある

MarkCopy: Copy

マーク済みfrom空間オブジェクトを転送ポインタが指すシェル内へコピー

to空間オブジェクトはto空間しか指さないという不変条件をライトバリアWrite_Copy(アルゴリズム17-6 (b))で保つ

ミューテータはまだfrom空間で動作中

Write_Copyは単にfrom空間オブジェクトへの更新を対応するto空間コピーへ伝播する

Copyフェーズ

Pre-Copyステップ: ライトバリアWrite_Copy(アルゴリズム17-6(b))をインストール

Copyステップ: マーク済みfrom空間オブジェクトを対応するto空間へコピー

これはロックフリーではなさそう

code: アルゴリズム17-7.py

# copyWordは使わないこと

def copyWord(p, q):

for i in range(MAX_RETRY):

$ toValue = *p

toValue = forward(toValue) # ポインタでなければ省略

$ *q = toValue

$ fromValue = *p

if toValue == fromValue:

return

$ LoadLinked(q)

$ toValue = *p

toValue = forward(toValue) # ポインタでなければ省略

$ StoreConditionally(q, toValue) # 理由なく失敗することはないと仮定

def copyWordSafe(p, q):

for ... # 同様

loop

$ LoadLinked(q)

$ toValue = *p

toValue = forward(toValue) # ポインタでなければ省略

$ if StoreCOnditionally(q, toValue):

return # SCが成功した

Flipフェーズ

PreFlipステップ: ライトバリアWrite_Flip(アルゴリズム17-6(c))をインストール

HeapFlipステップ: グローバル変数・new空間のオブジェクトがもつ参照をto空間のものへと反転させる

ThreadFlipステップ: ミューテータを1つずつ反転させる

スレッドを止めてスタック・レジスタの中の参照をto空間のものへと反転させ、スレッドを再スタートする

この間、ミューテータはfrom空間とto空間の両方を更新する

to空間へと反転済みのミューテータはfromAddressでもとのアドレスを取得する

Reclaimステップ: すべてのミューテータを反転した後、from空間とto空間からfrom空間へのハッシュ表を破棄する

Flipフェーズ中はミューテータがfrom空間とto空間の双方へ操作する可能性があるので、ポインタの等値判定ではto空間のポインタを比較する(アルゴリズム17-5(b))

フェーズの併合

RootMark, HeapMark/StackMark, Allocate, Copyは併合してReplicateフェーズ1つにまとめることができる

Write_MarkとWrite_Copyを組み合わせたライトバリアが必要

volatileフィールド

Sapphireのまとめ

並行コピーアルゴリズムの拡張

レプリケーション法との共通点が多い

スレッドを1つずつ反転できるので停止時間が最小限

volatileでないフィールドのリードバリアが必要ない

ミューテータはfrom空間とto空間の両方のコピーを書き換えて一貫性を保つ